package dataStructure.dac;

/**
 * @author lhn
 * @date 2024-09-10 10:48
 */

public class HanoiTower {
    public static void main(String[] args) {
//        hanoi(3, 'A', 'B', 'C');
        hanoi(9, 'A', 'B', 'C');
    }


    /**
     * 汉诺塔移动方案
     * 分治算法
     * @param n 盘子数量
     * @param a 起始柱
     * @param b 中间柱
     * @param c 目标柱
     */
    public static void hanoi(int n, char a, char b, char c) {
        // 如果只有一个盘子，直接移动即可
        if (n == 1) {
            System.out.println(n + "号盘子从" + a + "移动到" + c);
        } else {
            // n >= 2 , 看作两个盘子，最下面的一个，和上面的所有看做一个
            // 将上面的所有盘子从a移动到b，中间借用c
            hanoi(n - 1, a, c, b);  //a:n b:n - 1 c:空 这里是编号
            // 将最下面的盘子从a移动到c
            System.out.println(n + "号盘子从" + a + "移动到" + c);   //a:空 b:1~n-1 c:n 这里是编号
            hanoi(n - 1, b, a, c);  // 再将上面的所有盘子1-n-1从b移动到c，中间借用a
        }
        // 1.将n-1个盘子移动到中间柱，将第n个移动到目标柱
        // 2.将n-1个盘子从中间柱移动到目标柱，中间借用起始柱
    }
}
